//遍历一棵搜索二叉树，寻找出现的最多的节点
//若是一棵普通二叉树，可以使用map来记录每种节点的出现频率，然后排序。
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
#include <unordered_map>
#include <vector>
#include<algorithm>
using std::vector;
using std::unordered_map;
using std::pair;
using std::sort;
void traversal(TreeNode* root,unordered_map<int,int>& map){
    if(!root) return;
    traversal(root->left,map);
    map[root->val]++;           //记录出现频率
    traversal(root->right,map);
}
bool static cmp(const pair<int,int>& a,const pair<int,int>& b){
    return a.second>b.second;       //sort的排列函数，若a>b则是降序排列
}
vector<int> findMode(TreeNode* root) {
    vector<int> result;
    if(!root) return result;
    unordered_map<int,int> map;
    traversal(root,map);
    vector<pair<int,int>> vec(map.begin(),map.end());       //map的value值不可以排序，先将map转化为pair<int, int> 模板的数组
    sort(vec.begin(),vec.end(),cmp);                        //用cmp函数和sort排序value值（second就是value）
    result.push_back(vec[0].first);
    for(int i=1;i<vec.size()&&vec[0].second==vec[i].second;i++)
        result.push_back(vec[i].first);
    return result;


}



//也有只需遍历一次的方法
//对于二叉搜索树来说，中序遍历得到的是升序数组，那就可以只比较前后两个元素
//设置一个maxcount和count，当count等于maxcount，将节点放入result数组
//当count大于max，清空result数组并更新max
vector<int> result;
int Maxcount;
int count;
TreeNode* pre=nullptr;
void traversal(TreeNode* root,vector<int>& res){
    if(!root) return;
    traversal(root->left,res);  //左
    //中
    if(!pre) count=1;       //pre为空，说明root当前是最左边第一个节点
    else if(pre->val==root->val)
        count++;
    else count=1;

    //记录上一个节点
    pre=root;
    if(count==Maxcount) result.push_back(root->val);
    else if(count>Maxcount){
        result.clear();     //要清空result数组
        Maxcount=count;       //更新新的最大值

        result.push_back(root->val);
    }
    traversal(root->right,res); //右
    return ;
}
vector<int> findMode_(TreeNode* root){
    count=Maxcount=0;
    pre=nullptr;
    traversal(root,result);
    return result;
}


//迭代法
#include <stack>
using std::stack;
vector<int> findMode(TreeNode* root) {
int maxcount=0;
int count=0;
vector<int> result;
TreeNode* pre=nullptr;
TreeNode* cur=root;
stack<TreeNode*> st;
while(cur||!st.empty()){
    if(cur){
        st.push(cur);
        cur=cur->left;
    }
    else{
        cur=st.top();
        st.pop();
        if(!pre) count=1;
        else if(pre->val==cur->val) count++;
        else count=1;

        if(count==maxcount) result.push_back(cur->val);
        else if(count>maxcount) {
            maxcount=count;
            result.clear(); //清空数组

            result.push_back(cur->val);
        }

    pre=cur;                   //记录上一个节点
    cur=cur->right;
    }

}

return result;
}